#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int dp[100010];
    int pos = 0;
    int LIS(vector<int>& a) {

        for (auto x : a)
        {
            if (pos == 0 || x > dp[pos])
            {
                dp[++pos] = x;
            }
            else
            {
                int left = 1, right = pos;
                while (left < right)
                {
                    int mid = (left + right) >> 1;
                    if (dp[mid] >= x)
                        right = mid;
                    else
                        left = mid + 1;
                }
                dp[left] = x;
            }
        }
        return pos;
    }
};

int main()
{
	return 0;
}